package org.example.algorithm.array;

public class ProductExceptSelfSolution {
    public static void main(String[] args) {
        int[] nums = {1,2,3,4};
        ProductExceptSelfSolution solution = new ProductExceptSelfSolution();
        int[] ans = solution.productExceptSelf2(nums);
        for (int i=0;i<ans.length;i++) {
            System.out.println(ans[i]);
        }
    }

    public int[] productExceptSelf(int[] nums) {
        int len = nums.length;
        int[] prefixProduct = new int[len+1];
        prefixProduct[0] = 1;
        int[] suffixProduct = new int[len+1];
        suffixProduct[len] = 1;
        for (int i=0;i<len;i++) {
            prefixProduct[i+1] = prefixProduct[i] * nums[i];
        }
        for (int i=len-1;i>=0;i--) {
            suffixProduct[i] = suffixProduct[i+1] * nums[i];
        }
        int[] ans = new int[len];
        for (int i=0;i<len;i++) {
            ans[i] = prefixProduct[i] * suffixProduct[i+1];
        }
        return ans;
    }

    //优化内存占用
    public int[] productExceptSelf2(int[] nums) {
        int len = nums.length;
        int[] ans = new int[len];
        ans[0] = 1;
        for (int i=1;i<len;i++) {
            ans[i] = ans[i-1] * nums[i-1];
        }
        int rightBase = 1;
        for (int j=len-1;j>=0;j--) {
            ans[j] *= rightBase;
            rightBase *= nums[j];
        }
        return ans;
    }
}
